package com.springchang.algorithm.kmp;

import java.util.Arrays;

/**
 * KMP算法实现
 */
public class KMPAlgorithm {

    public static void main(String[] args) throws Exception {
        //1使用暴力破解获取字符串下标
        String source = "BBC ABCDAB ABCDABCDABDE";
        String search = "ABCDABD";
        System.out.println(bruteForce(source, search));

        //计算next表值
//        int[] next = next(search);
//        System.out.println(Arrays.toString(next));

        //用kmp算法求search字符串的下标
        System.out.println(kmp(source, search));
    }

    /**
     * 暴力求解字符串的下标,时间复杂度:O(n)
     * @param source
     * @param search
     * @return
     */
    public static int  bruteForce(String source, String search) throws Exception {
        byte[] sourceBytes = source.getBytes("UTF-8");
        byte[] searchBytes = search.getBytes("UTF-8");

        int i = 0;
        int j = 0;
        while(i < sourceBytes.length && j < searchBytes.length) {
            if(sourceBytes[i] == searchBytes[j]) {
                //如何source和search字符串匹配成功，则两个小标移动
                i++;
                j++;
            } else {
                //如果匹配不成功
                i = i - (j-1);
                j = 0;
            }
        }

        if(j == searchBytes.length) {
            return i-j;
        } else {
            return -1;
        }
    }

    public static int kmp(String source, String search) throws Exception {

        //获取next数组表
        int[] next = next(search);

        return kmpSearch(source, search, next);
    }

    public static int kmpSearch(String source, String search, int[] next) {

        for (int i = 0, j = 0; i < source.length(); i++) {
            while (j > 0 && source.charAt(i) != search.charAt(j)) {
                j = next[j-1];
            }

            if(source.charAt(i) == search.charAt(j)) {
                j++;
            }

            if(j == search.length()) {
                return i-j+1;
            }
        }
        return -1;
    }

    public static int[] next(String dest) {
        int[] next = new int[dest.length()];
        next[0] = 0;

        for (int i = 1, j = 0; i < dest.length(); i++) {
            while (j>0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }

            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }

        return next;
    }
}
